package com.jxm.linear;

/**
 * @Author: jxm
 * @Description: 约瑟夫问题
 * @Date: 2022/6/14 9:32
 * @Version: 1.0
 */
public class JosephQuestion {

    /**
     * 问题描述：传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决
     * 定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往
     * 后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡
     * 为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与
     * 第31个位置，从而逃过了这场死亡游戏 。
     * @param args
     */
    public static void main(String[] args) {
        //解决约瑟夫问题
        //构建环形链表，包含41个节点，分别存储1-41的值
        //用来记录首节点
        Node<Integer> first = null;
        //用来记录前一个节点
        Node<Integer> pre = null;
        for (int i = 1; i <= 41; i++) {
            //如果是第一个节点
            if(i==1){
                first = new Node<>(i,null);
                pre = first;
                continue;
            }
            //如果不是第一个节点
            Node<Integer> newNode = new Node<>(i,null);
            pre.next = newNode;
            pre = newNode;
            //如果是最后一个结点，那么需要让最后一个结点的下一个结点变为first，变为循环链表了
            if (i == 41){
                pre.next = first;
            }
        }

        //需要一个count计时器，模拟报数
        int count = 0;
        //遍历循环链表
        //记录每次遍历拿到的节点，默认从首节点开始
        Node<Integer> n = first;
        //记录当前节点的上一个节点
        Node<Integer> before = null;
        while (n!=n.next){ //TODO 只剩下一个节点，退出循环
            //模拟报数
            count++;
            //判断当前报数是不是3
            if(count == 3){
                //如果是3，则把当前节点删除调用，打印当前节点，重置count=0;让当前节点后移
                before.next = n.next; //让上一个节点的下一个节点指向当前节点的下一个节点，则表示删除当前节点
                System.out.print(n.item+",");
                n = n.next;
                count = 0;
            }else {
                //如果不是3,让before变为当前节点，让当前节点后移
                before = n;
                n = n.next;
            }
        }
        System.out.println("\n--------------");
        System.out.print(n.item+",");
    }

    //结点类
    private static class Node<T> {
        //存储数据
        T item;
        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item; this.next = next;
        }
    }
}
